package wells.tree;

public class Tree {
	private Node root;

	public void insert(int value) {

		root = insert(root, value);
	}

	private Node insert(Node x, int value) {
		if (x == null) {// 首次插入
			return new Node(value);
		}
		int xVal = x.value;

		if (value < xVal) {
			x.left = insert(x.left, value);
		} else if (value > xVal) {
			x.right = insert(x.right, value);
		} else {
			// do nothing
		}

		return x;

	}

	private class Node {

		private int value;
		private Node left, right;

		public Node(int value) {
			this.value = value;
			left = right = null;
		}
	}

	public Node select(int value) {
		return select(root, value);// work when BST is empty
	}

	private Node select(Node x, int value) {

		if (x == null)
			return null;

		int xVal = x.value;

		if (value < xVal)
			return select(x.left, value);
		else if (value > xVal)
			return select(x.right, value);
		else
			return x;

	}

	public void delete(int value) {

		root = delete(root, value);

	}

	private Node delete(Node x, int value) {

		if (x == null)
			return null;

		int xVal = x.value;

		if (value < xVal)
			x.left = delete(x.left, value);// 左子树
		else if (value > xVal)
			x.right = delete(x.right, value);// 右子树
		else {
			if (x.right == null)
				return x.left;
			if (x.left == null)
				return x.right;

			Node temp = x;// save the node to be deleted
			x = min(temp.right);// set x to point to its successor min(temp.right)
			x.right = deleteMin(temp.right);// set the right link of the successor to deleteMin(temp.right)
			x.left = temp.left;// set the left link of the successor to t.left
		}

		return x;
	}

	private Node min(Node x) {
		if (x.left == null)
			return x;
		return min(x.left);
	}

	private Node deleteMin(Node x) {

		if (x.left == null)
			return x.right;

		x.left = deleteMin(x.left);

		return x;
	}

	public static void main(String[] args) {
		Tree t = new Tree();
		System.out.println(t.select(3));
		t.insert(5);
		System.out.println(t.select(3));
		System.out.println(t.select(5));
		t.insert(3);
		t.insert(4);
		t.insert(6);
		System.out.println(t.select(4));
		
		t.delete(5);
		
		System.out.println(t);

	}
}
